#pragma once

#include <string>
#include <vector>

namespace solution_093
{

class Solution
{
public:
    std::vector<std::string> restoreIpAddresses(std::string s)
    {
        m_str.swap(s);

        std::string ip;
        ip.reserve(m_str.size() + 4);
        restore_sub(ip, 0, 0);

        return m_ips;
    }
private:
    void restore_sub(std::string& ip, int len, size_t first)
    {
        if (len == 4) {
            if (first == m_str.size()) {
                m_ips.push_back(ip);
                m_ips.back().pop_back();
            }
            return;
        }

        int rest_len = 4 - len;
        int rest_chs = m_str.size() - first;
        if (rest_chs < rest_len || rest_chs > rest_len * 3)
            return;

        int ip_num = 0;
        for (size_t i = first; i < first + 3 && i < m_str.size(); ++i) {
            if (i > first && m_str.at(first) == '0')
                break;

            auto ch = m_str.at(i);
            ip_num = ip_num * 10 + (ch - '0');
            if (ip_num > 255)
                break;

            ip.push_back(ch);
            ip.push_back('.');
            restore_sub(ip, len + 1, i + 1);
            ip.pop_back();
        }

        while (!ip.empty() && ip.back() != '.')
            ip.pop_back();
    }

    std::string m_str;
    std::vector<std::string> m_ips;
};

}  /* namespace solution_093 */
